
class BinaryTree {

  public static void main(String[] a) {
    System.out.println(new BT().Start());
  }
}

// This class invokes the methods to create a tree,
// insert, delete and serach for  elements on it
class BT {

  public int Start() {
    Tree root;
    boolean ntb;
    int nti;

    root = new Tree();
    ntb = root.Init(16);
    ntb = root.Print();
    System.out.println(100000000);
    ntb = root.Insert(8);
    ntb = root.Print();
    ntb = root.Insert(24);
    ntb = root.Insert(4);
    ntb = root.Insert(12);
    ntb = root.Insert(20);
    ntb = root.Insert(28);
    ntb = root.Insert(14);
    ntb = root.Print();
    System.out.println(root.Search(24));
    System.out.println(root.Search(12));
    System.out.println(root.Search(16));
    System.out.println(root.Search(50));
    System.out.println(root.Search(12));
    ntb = root.Delete(12);
    ntb = root.Print();
    System.out.println(root.Search(12));

    return 0;
  }
}

class Tree {

  Tree left;
  Tree right;
  int key;
  boolean has_left;
  boolean has_right;
  Tree my_null;

  // Initialize a node with a key value and no children
  public boolean Init(int v_key) {
    key = v_key;
    has_left = false;
    has_right = false;
    return true;
  }

  // Update the right child with rn
  public boolean SetRight(Tree rn) {
    right = rn;
    return true;
  }

  // Update the left child with ln
  public boolean SetLeft(Tree ln) {
    left = ln;
    return true;
  }

  public Tree GetRight() {
    return right;
  }

  public Tree GetLeft() {
    return left;
  }

  public int GetKey() {
    return key;
  }

  public boolean SetKey(int v_key) {
    key = v_key;
    return true;
  }

  public boolean GetHas_Right() {
    return has_right;
  }

  public boolean GetHas_Left() {
    return has_left;
  }

  public boolean SetHas_Left(boolean val) {
    has_left = val;
    return true;
  }

  public boolean SetHas_Right(boolean val) {
    has_right = val;
    return true;
  }

  // This method compares two integers and
  // returns true if they are equal and false
  // otherwise
  public boolean Compare(int num1, int num2) {
    boolean ntb;
    int nti;

    ntb = false;
    nti = num2 + 1;
    if (num1 < num2) {
      ntb = false;
    } else if (!(num1 < nti)) {
      ntb = false;
    } else {
      ntb = true;
    }
    return ntb;
  }

  // Insert a new element in the tree
  public boolean Insert(int v_key) {
    Tree new_node;
    boolean ntb;
    boolean cont;
    int key_aux;
    Tree current_node;

    new_node = new Tree();
    ntb = new_node.Init(v_key);
    current_node = this;
    cont = true;
    while (cont) {
      key_aux = current_node.GetKey();
      if (v_key < key_aux) {
        if (current_node.GetHas_Left()) {
          current_node = current_node.GetLeft();
        } else {
          cont = false;
          ntb = current_node.SetHas_Left(true);
          ntb = current_node.SetLeft(new_node);
        }
      } else {
        if (current_node.GetHas_Right()) {
          current_node = current_node.GetRight();
        } else {
          cont = false;
          ntb = current_node.SetHas_Right(true);
          ntb = current_node.SetRight(new_node);
        }
      }
    }
    return true;
  }

  // Delete an element from the tree
  public boolean Delete(int v_key) {
    Tree current_node;
    Tree parent_node;
    boolean cont;
    boolean found;
    boolean is_root;
    int key_aux;
    boolean ntb;

    current_node = this;
    parent_node = this;
    cont = true;
    found = false;
    is_root = true;
    while (cont) {
      key_aux = current_node.GetKey();
      if (v_key < key_aux) {
        if (current_node.GetHas_Left()) {
          parent_node = current_node;
          current_node = current_node.GetLeft();
        } else {
          cont = false;
        }
      } else if (key_aux < v_key) {
        if (current_node.GetHas_Right()) {
          parent_node = current_node;
          current_node = current_node.GetRight();
        } else {
          cont = false;
        }
      } else {
        if (is_root) {
          if ((!current_node.GetHas_Right()) &&
                  (!current_node.GetHas_Left())) {
            ntb = true;
          } else {
            ntb = this.Remove(parent_node, current_node);
          }
        } else {
          ntb = this.Remove(parent_node, current_node);
        }
        found = true;
        cont = false;
      }
      is_root = false;
    }
    return found;
  }

  // Check if the element to be removed will use the
  // righ or left subtree if one exists
  public boolean Remove(Tree p_node, Tree c_node) {
    boolean ntb;
    int auxkey1;
    int auxkey2;

    if (c_node.GetHas_Left()) {
      ntb = this.RemoveLeft(p_node, c_node);
    } else if (c_node.GetHas_Right()) {
      ntb = this.RemoveRight(p_node, c_node);
    } else {
      auxkey1 = c_node.GetKey();
      //auxtree01 = p_node.GetLeft() ;
      //auxkey2 = auxtree01.GetKey() ;
      auxkey2 = (p_node.GetLeft()).GetKey();
      if (this.Compare(auxkey1, auxkey2)) {
        ntb = p_node.SetLeft(my_null);
        ntb = p_node.SetHas_Left(false);
      } else {
        ntb = p_node.SetRight(my_null);
        ntb = p_node.SetHas_Right(false);
      }
    }
    return true;
  }

  // Copy the child key to the parent until a leaf is
  // found and remove the leaf. This is done with the
  // right subtree
  public boolean RemoveRight(Tree p_node, Tree c_node) {
    boolean ntb;

    while (c_node.GetHas_Right()) {
      //auxtree01 = c_node.GetRight() ;
      //auxint02 = auxtree01.GetKey();
      //ntb = c_node.SetKey(auxint02);
      ntb = c_node.SetKey((c_node.GetRight()).GetKey());
      p_node = c_node;
      c_node = c_node.GetRight();
    }
    ntb = p_node.SetRight(my_null);
    ntb = p_node.SetHas_Right(false);
    return true;
  }

  // Copy the child key to the parent until a leaf is
  // found and remove the leaf. This is done with the
  // left subtree
  public boolean RemoveLeft(Tree p_node, Tree c_node) {
    boolean ntb;

    while (c_node.GetHas_Left()) {
      //auxtree01 = c_node.GetLeft() ;
      //auxint02 = auxtree01.GetKey();
      //ntb = c_node.SetKey(auxint02);
      ntb = c_node.SetKey((c_node.GetLeft()).GetKey());
      p_node = c_node;
      c_node = c_node.GetLeft();
    }
    ntb = p_node.SetLeft(my_null);
    ntb = p_node.SetHas_Left(false);
    return true;
  }

  // Search for an elemnt in the tree
  public int Search(int v_key) {
    boolean cont;
    int ifound;
    Tree current_node;
    int key_aux;

    current_node = this;
    cont = true;
    ifound = 0;
    while (cont) {
      key_aux = current_node.GetKey();
      if (v_key < key_aux) {
        if (current_node.GetHas_Left()) {
          current_node = current_node.GetLeft();
        } else {
          cont = false;
        }
      } else if (key_aux < v_key) {
        if (current_node.GetHas_Right()) {
          current_node = current_node.GetRight();
        } else {
          cont = false;
        }
      } else {
        ifound = 1;
        cont = false;
      }
    }
    return ifound;
  }

  // Invoke the method to really print the tree elements
  public boolean Print() {
    Tree current_node;
    boolean ntb;

    current_node = this;
    ntb = this.RecPrint(current_node);
    return true;
  }

  // Print the elements of the tree
  public boolean RecPrint(Tree node) {
    boolean ntb;

    if (node.GetHas_Left()) {
      //auxtree01 = node.GetLeft() ;
      //ntb = this.RecPrint(auxtree01);
      ntb = this.RecPrint(node.GetLeft());
    } else {
      ntb = true;
    }
    System.out.println(node.GetKey());
    if (node.GetHas_Right()) {
      //auxtree01 = node.GetRight() ;
      //ntb = this.RecPrint(auxtree01);
      ntb = this.RecPrint(node.GetRight());
    } else {
      ntb = true;
    }
    return true;
  }
}
   
